package set;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class SubSets78 {

    @Test
    public void testSubsetsRecursively() {
        subsetsRecursively0(new int[]{1, 2, 3, 4});
        subsetsRecursively1(new int[]{1, 2, 3, 4});
    }

    @Test
    public void testSubsetsLooply() {
        subsetsLooply(new int[]{1});
        subsetsLooply(new int[]{1, 2});
        subsetsLooply(new int[]{1, 2, 3});
        subsetsLooply(new int[]{1, 2, 3, 4});
    }

    //两路递归: redo at 2022.03.12
    public static class TwoWayRecursion {
        // redo at 2022.03.12
        public List<List<Integer>> subsets(int[] nums) {
            List<List<Integer>> subsets =  new ArrayList<>((int)Math.pow(2, nums.length));
            generateSubsetsRecursively(nums, 0, new ArrayList<>(nums.length), subsets);
            return subsets;
        }

        // 两路回溯递归, 每个元素都有两种选择策略: 选或不选.
        // k表示当前在哪个下标处做决策. 只有当k=nums.length时, 才能够将结果加入结果集. 因此此时决策才完了. 中途不能加入结果集.
        // 也可以多路递归, 理解起来相对复杂.
        public void generateSubsetsRecursively(
                int[] nums,
                int k,
                List<Integer> subset,
                List<List<Integer>> subsets) {

            if (k >= nums.length) {
                // 遍历过最后一个元素了, 保存结果
                subsets.add(new ArrayList<>(subset));
                return;
            }

            // 不选择k
            generateSubsetsRecursively(nums, k+1, subset, subsets);

            // 选择k
            subset.add(nums[k]);
            generateSubsetsRecursively(nums, k+1, subset, subsets);
            // 选择k后回溯. ArrayList移除最后一个元素时, 不会copy数组.
            subset.remove(subset.size()-1);
        }
    }
    //--------两路递归结束 -------------

    public List<List<Integer>> subsetsLooply(int[] nums) {
        List<List<Integer>> result = new ArrayList<>(2 << nums.length);
        LinkedList<Integer> subsetOfIndex = new LinkedList<>();

        // add empty set
        result.add(getSubsetByIndex(nums, subsetOfIndex));
        int index = 0;
        while (true) {
            subsetOfIndex.add(index);
            result.add(getSubsetByIndex(nums, subsetOfIndex));
            index++;

            // 条件是当前index已经到最后了, 不是subsetOfIndex满了
            if (index >= nums.length) {
                // 删除最后一个
                subsetOfIndex.removeLast();

                if (subsetOfIndex.size() > 0) {
                    // 还有元素, 倒数第二个加1, 只能在下一轮循环被加入subsetOfIndex
                    index = subsetOfIndex.removeLast() + 1;
                } else {
                    // 没有元素了, 遍历完成
                    break;
                }
            }
        }
        print(nums, result);
        return result;
    }
    public List<Integer> getSubsetByIndex(int[] nums, List<Integer> subsetOfIndex) {
        List<Integer> subset = new ArrayList<>(subsetOfIndex.size());
        for (int index: subsetOfIndex) {
            subset.add(nums[index]);
        }
        return subset;
    }

    public List<List<Integer>> subsetsRecursively0(int[] nums) {
        List<List<Integer>> result = new ArrayList<>(2 << nums.length);
        doSubsetsRecursively0(nums, 0, new LinkedList<>(), result);
        print(nums, result);
        return result;
    }

    public void doSubsetsRecursively0(int[] nums, int startIndex, LinkedList<Integer> subset, List<List<Integer>> result) {
        result.add(new ArrayList<>(subset));
        // 不会重复或遗漏
        for (int i = startIndex; i < nums.length; i++) {
            subset.add(nums[i]);
            doSubsetsRecursively0(nums, i+1, subset, result);
            subset.removeLast();
        }
    }

    public List<List<Integer>> subsetsRecursively1(int[] nums) {
        List<List<Integer>> result = new ArrayList<>(2 << nums.length);
        doSubsetsRecursively1(nums, 0, new LinkedList<>(), result);
        print(nums, result);
        return result;
    }

    public void doSubsetsRecursively1(int[] nums, int index, LinkedList<Integer> subset, List<List<Integer>> result) {
        if (index == nums.length) {
            result.add(new ArrayList<>(subset));
            return;
        }
        subset.add(nums[index]);
        doSubsetsRecursively1(nums, index+1, subset, result);
        subset.removeLast();
        doSubsetsRecursively1(nums, index+1, subset, result);
    }

    public void print(int[] nums, List<List<Integer>> result) {
        System.out.println("--------------------------");
        System.out.format("nums: %s, result.size: %d\n", Arrays.toString(nums), result.size());
        for (List<Integer> subset: result) {
            System.out.println(subset);
        }
        System.out.println();
    }
}
